package com.erbao.datastructurearithmetic.tyro;

import java.util.HashSet;
import java.util.Random;

/**
 * @author CaoBaoYin
 * @since 21/8/1 18:41
 */
public class Class5 {

    public static void main(String[] args) {
        /*验证位图*/
        /*int testTimes = 1000000;
        int maxValue = Integer.MAX_VALUE;
        Random random = new Random();
        BitMap bitMap = new BitMap(maxValue);
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < testTimes; i++) {
            int value = random.nextInt(maxValue);
            double op = Math.random();
            if (op < 0.33){
                bitMap.add(value);
                set.add(value);
            } else if (op < 0.66){
                bitMap.remove(value);
                set.remove(value);
            } else {
                if (bitMap.contains(value) != set.contains(value)) {
                    System.out.println("出错了");
                    break;
                }
            }
        }

        for (int i = 0; i < maxValue; i++) {
            if (bitMap.contains(i) != set.contains(i)) {
                System.out.println("出错了");
                break;
            }
        }

        System.out.println("nice");*/

        System.out.println(divide(Integer.MIN_VALUE, -4));
        System.out.println(Integer.MIN_VALUE/-4);

        /*int testTimes = 10000000;
        Random random = new Random();
        for (int i = 0; i < testTimes; i++) {
            int a = random.nextInt();
            int b = random.nextInt();
            if (multiply(a, b) != (a * b)) {
                System.out.println("出错了：a="+a+", b="+b);
                break;
            }
        }
        System.out.println("nice");*/
    }

    /**
     * 计算 a/b
     */
    private static int divide(int a, int b) {
        if (a == Integer.MIN_VALUE & b == Integer.MIN_VALUE) {
            return 1;
        } else if (b == Integer.MIN_VALUE) {// 隐含条件a!=Integer.MIN_VALUE
            return 0;
        } else if (a == Integer.MIN_VALUE) {// 隐含条件b!=Integer.MIN_VALUE
            if (b == negNum(1)) {// b == -1,结果无法在计算机中显示,规定可以返回Integer.MAX_VALUE;
                return Integer.MAX_VALUE;
            } else {
                int t = add(a, 1);
                int res = div(t, b);

                /*最后的余数跟1*/
                // b 是正数 不兼容
                // return sub(a, multiply(res, b)) == b ? add(res, 1) : res;
                //如果余数够一个b，add的两个参数正负号就一样了
                return add(res, div(sub(a, multiply(res, b)), b));
            }
        } else {// a、b都不等Integer.MIN_VALUE
            return div(a, b);
        }
    }

    private static int div (int a, int b){
        // 需要优先处理 integer的最小值 最小值相反数是无法得到正确结果的
        int x = isNeg(a) ? negNum(a) : a;
        int y = isNeg(b) ? negNum(b) : b;

        /*避免b左移,如果移到了符号位，采取a右移代替
        * 每次移动位数肯定是越来越小，逆向循环只需一遍
        * 右移30位开始而不是31位，是因为知道是个整数，符号位是0*/
        int res = 0;
        for (int i = 30; i >= 0 ; i = sub(i, 1)) {
            if ((x >> i) >= y) {
                res  = add(res, 1 << i);
                x = sub(x, y << i);
            }
        }
        return isNeg(a) ^ isNeg(b) ? negNum(res) : res;
    }

    private static int negNum (int n) {
        return add(~n, 1);
    }

    private static boolean isNeg(int a) {
        return a < 0;
    }

    private static int multiply (int a, int b){
        if (a == 0 || b == 0){
            return 0;
        }
        if (a == 1 || b == 1){
            return a == 1 ? b : a;
        }

        int res = 0;
        while ( b != 0) {
            if ((b & 1) == 1) {
                res = add(res, a);
            }
            b >>>= 1;//避免负数右移，1 补位，死循环
            a <<= 1;
        }
        return res;
    }

    private static int sub (int a, int b){
        return add(a, add(~b, 1));
    }

    private static int add (int a, int b){
        if (a == 0 || b == 0) {
            return a == 0 ? b : a;
        }

        int resultWithoutCarry = a;
        // 左移一位如果越界了，说明这两个数求和也会超出最大值
        int carry = b;
        while (carry != 0) {
            resultWithoutCarry = a ^ b;
            carry = (a & b) << 1;
            a = resultWithoutCarry;
            b = carry;
        }
        return resultWithoutCarry;
    }

    /**
     * 表示范围是0 <= value <= max
     */
    private static class BitMap {
        private long[] bits;

        public BitMap(int maxValue) {
            /*每一位表示一个整数，数组中的0位置就表是0--63,1位置表示64--127……
            * 右移6位，相当于maxValue/64，能用位运算代替，优先使用位运算，位运算比算术运算快十倍以上*/
            bits = new long[(maxValue >> 6) + 1];
        }

        public int add(int value){
            /*value在数组中的角标位置：value >> 6
            * 整数后一定要写“L”
            * value % 64 相当于 value & 63。% 取余预算。&取代，只适用于2的倍数
            * 左移，表示该整数的位改为1
            * 异或是保证只修改64位中的当前位置变为1，其他位保持原样.
            * 1|0=1 一真则真*/
            bits[value >> 6] |= 1L << (value & 63);
            return value;
        }

        public int remove(int value){
            /*取非做与运算，当前位置改为0，其他位置不变*/
            bits[value >> 6] &= ~(1L << (value & 63));
            return value;
        }

        public boolean contains(int value){
            /*判断当前位置是1还是0，其他位置忽略*/
            return (bits[value >> 6] & (1L << (value & 63))) != 0;
        }
    }

}
